import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-21
 * Time: 23:32
 */
public class Solution {

    public void swap(int []arr,int index1,int index2){
        int temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }
    //翻转
    public void reverse(int[] arr,int begin,int end){
        while(begin<end){
            //交换
            swap(arr,begin,end);
            begin++;
            end--;
        }
    }

    public void nextPermutation(int[] nums) {
        int flag=0;
        int length=nums.length;
        int index1=-1;
        int index2=-1;
        //从后往前找第一个不是降序的数
        //这个数靠右,交换后的结果相差就比较少
        for(int i=length-1;i>0;i--){
            if(nums[i]>nums[i-1]){
                index1=i-1;
                break;
            }
        }
        if(index1==-1){
            //第一遍没有找到,说明整个数组是降序的,从前到后反转之后直接返回
            reverse(nums,0,length-1);
            return ;
        }
        //找到index1
        //再从后往前找比index1对应的值大但最接近的值
        //这样交换后的结果相差就比较少
        for(int i=length-1;i>index1;i--){
            if(nums[i]>nums[index1]){
                index2=i;
                break;
            }
        }
        swap(nums,index1,index2);
        //交换完之后,后面的数字升序排列才是最小的
        reverse(nums,index1+1,length-1);
    }
}